package com.data_structure_test.linklist;

import java.util.HashSet;
import java.util.Set;

public class LinkedList {

    public static void main(String[] args){

        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(4);

        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(3);
        l2.next.next = new ListNode(4);
        l2.next.next.next = new ListNode(3);
        l2.next.next.next.next = new ListNode(4);

        LinkedList test = new LinkedList();
        //test.mergeTwoLists(l1,l2);
        //test.deleteDuplicates(l2);

    }


    public ListNode deleteDuplicates(ListNode head) {

        Set<Integer> exists = new HashSet<>();
        ListNode sentinel = new ListNode(0);
        sentinel.next = head;
        ListNode res = sentinel;
        ListNode tmp;
        while((tmp = sentinel.next) != null){
            if(!exists.contains(tmp.val)){
                exists.add(tmp.val);
                sentinel = sentinel.next;
            }else{
                sentinel.next = tmp.next;
            }
        }

        return res.next;


    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(0);
        ListNode tmpRes = res;
        while(l1 != null || l2 != null){

            if(l2 == null){
                tmpRes.next = l1;
                tmpRes = tmpRes.next;
                l1 = l1.next;
                continue;
            }

            if(l1 == null){
                tmpRes.next = l2;
                tmpRes = tmpRes.next;
                l2 = l2.next;
                continue;
            }

            if(l1.val < l2.val){

                tmpRes.next = l1;
                tmpRes = tmpRes.next;
                l1 = l1.next;
            }else{
                tmpRes.next = l2;
                tmpRes = tmpRes.next;
                l2 = l2.next;
            }

        }
        return res.next;

    }
}
